package com.yoshino.leetcode.interview150.matrix;

import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean isValidSudoku(char[][] board) {
        // 记录某行，某位数字是否已经被摆放
        boolean[][] row = new boolean[9][9];
        // 记录某列，某位数字是否已经被摆放
        boolean[][] col = new boolean[9][9];
        // 记录某 3x3 宫格内，某位数字是否已经被摆放
        boolean[][] block = new boolean[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '1';
                    int blockIndex =  i / 3 * 3 + j / 3;
                    if (row[i][num] || col[j][num] || block[blockIndex][num]) {
                        return false;
                    } else {
                        row[i][num] = true;
                        col[j][num] = true;
                        block[blockIndex][num] = true;
                    }
                }
            }
        }
        return true;
    }

    public List<Integer> spiralOrder(int[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length, total = rows * cols, row = 0, col = 0, nr, nc, ind = 0;
        List<Integer> res = new ArrayList<>();
        boolean[][] visited = new boolean[rows][cols];
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int i = 0; i < total; ) {
            if (visited[row][col]) {
                nr = row + directions[ind][0];
                nc = col + directions[ind][1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc]) {
                    // 有效的
                    row = nr;
                    col = nc;
                } else {
                    ind = (ind + 1) % 4;
                }
            } else {
                // 没有访问过
                res.add(matrix[row][col]);
                visited[row][col] = true;
                i++;
            }
        }
        return res;
    }

    public void setZeroes(int[][] matrix) {
        // 标记法
        int rows = matrix.length, cols = matrix[0].length;
        boolean[] zeroR = new boolean[rows], zeroC = new boolean[cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 0) {
                    zeroR[i] = true;
                    zeroC[j] = true;
                }
            }
        }
        for (int i = 0; i < rows; i++) {
            if (zeroR[i]) {
                for (int j = 0; j < cols; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int j = 0; j < cols; j++) {
            if (zeroC[j]) {
                for (int i = 0; i < rows; i++) {
                    matrix[i][j] = 0;
                }
            }
        }
    }

    public void gameOfLife(int[][] board) {
        int[] DR = {0, 0, 1, -1, 1, 1, -1, -1}, DC = {1, -1, 0, 0, 1, -1, 1, -1};
        int rows = board.length, cols = board[0].length, nr, nc;
        // 复制
        int[][] res = new int[rows][cols];
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                res[row][col] = board[row][col];
            }
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int liveCells = 0;
                for (int m = 0; m < 8; m++) {
                    nr = i + DR[m];
                    nc = j + DC[m];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && res[nr][nc] == 1) {
                        liveCells++;
                    }
                }

                if (board[i][j] == 1 && (liveCells < 2 || liveCells > 3)) {
                    board[i][j] = 0;
                } else if (board[i][j] == 0 && liveCells == 3) {
                    board[i][j] = 1;
                }
            }
        }
    }

    public void rotate(int[][] matrix) {
        int length = matrix.length, n = length - 1;
        for (int i = 0; i < length / 2; i++) {
            // 避免重复反转
            for (int j = i; j < length - 1 - i; j++) {
                convert(matrix, i, j, n);
            }
        }
    }

    private void convert(int[][] matrix, int i, int j, int n) {
        int temp = matrix[i][j];
        // 画图
        matrix[i][j] = matrix[n - j][i];
        matrix[n - j][i] = matrix[n - i][n - j];
        matrix[n - i][n - j] = matrix[j][n - i];
        matrix[j][n - i] = temp;
    }
}